# -*- encoding: utf-8 -*-


class Link(object):
    def __init__(self, x):
        self.previous = None
        self.next = None
        self.value = x

    def display_link(self):
        print('{}'.format(self.value), end=" ")


class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def is_empty(self):
        return self.head is None

    def insert_head(self, x):
        new_link = Link(x)
        if self.is_empty():
            self.tail = new_link
        else:
            self.head.previous = new_link
        new_link.next = self.head
        self.head = new_link

    def delete_head(self):
        if not self.is_empty():
            temp = self.head
            self.head = self.head.next
            if self.head is None:
                self.tail = None
            else:
                self.head.previous = None
            return temp

    def insert_tail(self, x):
        new_link = Link(x)
        self.tail.next = new_link
        new_link.previous = self.tail
        self.tail = new_link

    def delete_tail(self):
        temp = self.tail
        if not self.is_empty():
            if self.tail.previous:
                self.tail.previous.next = None
                self.tail = self.tail.previous
            else:
                self.tail = None
        return temp

    def delete(self, x):
        if not self.is_empty():
            current = self.head
            while current.value != x:
                current = current.next
                if current is None:
                    return
            if current == self.head:
                self.delete_head()
            elif current == self.tail:
                self.delete_tail()
            else:
                current.previous.next = current.next
                current.next.previous = current.previous

    def len(self):
        n = 0
        current = self.head
        while current:
            n += 1
            current = current.next
        return n

    def display(self):
        current = self.head
        while current:
            current.display_link()
            current = current.next
        print()

    def display_reverse(self):
        current = self.tail
        while current:
            current.display_link()
            current = current.previous
        print()


def main():
    obj = LinkedList()
    print('insert 1st head')
    obj.insert_head(2)
    print('insert 2nd head')
    obj.insert_head(1)
    print('insert 1st tail')
    obj.insert_tail(3)
    print('insert 2nd tail')
    obj.insert_tail(4)
    print('display link')
    obj.display()
    print('display reverse link')
    obj.display_reverse()
    print(obj.len())
    print('delete head')
    obj.delete_head()
    print('delete tail')
    obj.delete_tail()
    print('display link')
    obj.display()
    print('display reverse link')
    obj.display_reverse()
    print(obj.len())


if __name__ == '__main__':
    main()
